1. Field of the Invention
The present invention relates generally to the field of arbitration, and more specifically to methods and apparatus for arbitrating requester access requests for access to multiple resources or channels in a high speed data transmission environment.
2. Description of the Related Art
Data communication networks receive and transmit ever increasing amounts of data. Data is transmitted from an originating entity or requester, through the network to a destination, such as a channel or resource. Along this path may be multiple points that receive data, typically in the form of packets or data frames, and along each point data must be routed to the next point in the network in a rapid and efficient manner. Certain protocols or standards may be employed in transferring data from one point to another, and such standards enable hardware and software employing different configurations to effectively receive and transfer the data. Such standards include, but are not limited to, Utopia, X.25, and other standards promulgated by the ITU and ANSI.
The points throughout the data network operate to receive data requests or packets from various requesters and provide results or satisfy requests in an orderly and efficient manner. Requests may arrive synchronously or asynchronously, and requests may be for access to multiple resources or channels or to particular sets of resources or channels. For example, multiple requesters may transmit data seeking access multiple times each second to channel one, while a single requestor may transmit data on an approximate hourly basis requesting access to channel two. A single requester may request access to multiple resources at one time. The hardware or software at the data transmission point in the data network acts as a traffic officer, deciding which data packets receive priority in transmission while requiring others to wait.
The traditional hardware or software used to perform this access control function has been a form of arbiter, typically a round robin arbiter. Other designs have been employed, including lookup tables, FIFO arrangements, and other designs known to those skilled in the art. A round robin arbiter receives requests from requesters and allocates those requests among the channels or resources sequentially according to requester position. For example, if requestors one through five seek access to a Channel A, and requesters one through four transmit multiple requests while requester five transmits one request, the round robin arbiter allows access in an ordered manner to requestors one through five and subsequently to one through four until all requests have been satisfied. If requester five has not made a request, the round robin arbiter skips requester five and goes on to the next requestor in sequence. If requester five adds a request at some point during arbitration, this new request becomes part of the round robin process and is satisfied sequentially. This differs from a FIFO arrangement in that input channels are individually queued in round robin arbitration, while FIFO employs a single queue, and the first request received is the first request satisfied.
The problems with the round robin arrangement include the inability to prioritize the arriving requests in an efficient manner and the difficulty accounting for priorities among the requests. It is desirable for certain requests or certain requesters to receive higher priority than others. Round robin arbitration simply goes through the requests from the requestors in order and allows them access to the resource when it is the requestor's “turn.” In the foregoing example, if requestor one is a high priority requestor generating a large number of requests in a short amount of time while requester five is a lower priority, the round robin arbitration will grant the request from requester five in round robin fashion every time the requester five queue includes a request. This granting of a slot to low priority requestor five will hinder system performance by slowing the higher priority requester one requests. The result is delays to priority requests and lower throughput at the data transfer point.
Round robin arbiters are simple, straightforward, and relatively well known. To the extent a simple, straightforward and relatively well known design could be employed in a weighted arbitration scheme, such a design would be beneficial.
Based on the foregoing, it would be desirable to provide a system that overcomes the limitations associated with round robin arbiters with respect to priorities associated with incoming requests.